1 Définition

In data analysis, anomaly detection (also outlier detection) is the identification of rare items, events or observations which raise suspicions by differing significantly from the majority of the data.

• Dans le domaine de l’apprentissage non-supervisée (pas de « label »)
• Pour détecter des données qui sont atypiques pour la distribution de probabilité observée
• Difficulté: on ne connait pas la distribution sous-jacente des données
• L’algorithme doit donc apprendre une métrique appropriée pour détecter les anomalies

2 Exemples d’applications

• Transactions bancaires (une anomalie est vue comme une fraude potentielle)
• Surveillance des données physiologiques d’un malade (l’anomalie est un problème de santé possible)
• Détection de défauts dans des chaines de production

3 Types de méthodes de détection d’anomalies

• Les techniques statistiques
  • Construisent un modèle avec un intervalle de confiance à partir des données existantes
  • Les nouvelles données qui ne correspondent pas à ce modèle seront considérées anormales
  • Peuvent être paramétriques ou non-paramétriques
• Les techniques basées sur la proximité
  • Regroupent les techniques basées sur les plus proches voisins et sur le clustering
• Les techniques basées sur le deep learning
  • Auto-encodeurs
  • One-Class Neural Networks
• Les autres techniques
  • Machines à vecteur de support
  • Réseaux de neurones
  • Etc.

4 Approches populaires

• Local Outlier Factor (LOF)
  • On attribue à chaque donnée un score (LOF) fondé sur le ratio obtenu en comparant la densité locale d’une observation à celle de ses plus proches voisins. Les points observés ayant une faible densité locale comparativement à leurs plus proches voisins sont considérés comme des anomalies.
• Isolation Forest
  • Cet algorithme cherche à isoler les observations avec des coupures successives et aléatoires (arbre de décision). Les points faciles à isoler (qui sont seuls ou dans une région à faible densité) sont considérés comme des anomalies. Les points issues de zones à forte densité (durs à isoler) sont considérées comme normaux.
• One-class SVM
  • Il s’agit de définir un hyper-plan (un plan dans un espace 3+D) qui rassemble la majeure partie des données d’un côté (la normalité), et peu ou pas de l’autre (les anomalies). Le plan agit comme frontière décisionnelle pour les nouvelles données.

5 Détection d’anomalies avec données télématique

• Semiautonomous Vehicle Risk Analysis: A Telematics-Based Anomaly Detection Approach
  • Étudie la structure de risque des véhicule semi-autonome et utilise un modèle de détection des anomalies basé sur la télématique pour évaluer les profils de risque.
  • An unsupervised multivariate Gaussian (MVG) based anomaly detection method is used to identify abnormal driving patterns based on accelerometer and GPS sensors of manually driven vehicles.
  • Ils ont l’air d’avoir de l’information plus détaillée que nous.
  • Article introuvable gratuitement (DOI: 10.1111/risa.13217)
• Detecting Anomalous Taxi Trajectories from GPS Traces
  • Ils détectent les anomalies dans les trajets de taxis équipés de GPS.
  • Pour éviter la fraude, entre autres: certains chauffeurs prennenet des détours inutiles.
  • Utilisent du “isolation-based anomaly detection”.
• Coupled IGMM-GANs with Applications to Anomaly Detection in Human Mobility Data
  • Développent une méthode qui permet de créer des trajets synthétiques mais réalistes, ce qui facilite la détection d’anomalies par la suite.

6 Détection de fraude en assurance automobile

“The literature on unsupervised auto insurance fraud detection is extremely sparse.”

• Auto insurance fraud detection using unsupervised spectral ranking for anomaly
  • Détection de fraude pour les réclamations en assurance auto.
  • Proposent “a new unsupervised spectral ranking method for anomaly (SRA)”, qui permet de faire un “ranking” des anomalies.
  • Leur méthode n’utilise pas de labels (car non-supervisé), mais il ont un jeu de données avec des labels qui permet d’évaluer la performance.
• Using Kohonen’s self-organizing feature map to uncover automobile bodily injury claims fraud
  • Essaient de détecter les fraudes de réclamation en assurance auto avec un genre de réseau de neurones appelé “self-organizing feature map”.
• Fraud classification using principal component analysis of RIDITs
  • Détection de fraudes de réclamations avec analyse des composantes principales sur les scores RIDIT (ils appellent leur méthode PRIDIT).
  • Leur méthode permet à la fois de déterminer la “force” des variables et de donner un score de suspicion à chaque réclamation.
• A robust unsupervised method for fraud rate estimation
  • Proposent une nouvelle méthode pour estimer le taux de fraude, appelée PRIDIT-based Fraud Rate Estimation.
  • Examinent le de fraudes dans une population de réclamations.
• Assessing consumer fraud risk in insurance claims: an unsupervised learning technique using discrete and continuous predictor variables
  • Extension de la méthode PRIDIT, mais pour d’autres types de prédicteurs (catégoriel ordinal, par exemple).

7 Surveys et reviews sur la détection d’anomalies

• Outlier Detection for Temporal Data: A Survey
• A review on outlier/anomaly detection in time series data
• A survey of anomaly detection techniques in financial domain

8 Différentes facettes de la détection d’anomalies pour données temporelles

9 Littérature « Single Time Series »

10 Littérature « Time Series Database »

11 Littérature « Data streams »

12 Autre articles

• RLAD: Time Series Anomaly Detection through Reinforcement Learning and Active Learning (2021)
• Robust and Unsupervised Anomaly Detection for Multivariate Dataset (2020)
• Outlier Detection in Multivariate Data (2015)
• ICSOutlier: Unsupervised Outlier Detection for Low-Dimensional Contamination Structure (2018)
• REPPlab: An R package for detecting clusters and outliers using exploratory projection pursuit (2018)
• Ensembles for unsupervised outlier detection: challenges and research questions a position paper (2014)

13 Détection d’anomalies non-supervisée

• Credit Card Fraud Detection using autoencoder based clustering (2018)
  • Jeu de données Européen contenant 285 000 transactions sur 2 jours.
  • Les données consistent en 28 composantes principales (pour raisons de confidentialité) + « time » et « amount ». Probablement le jeu de données Kaggle.
  • Utilisation d’un auto-encodeur (donc pas besoin de labels), mais ils mesurent la performance en utilisant des labels.
  • Pas un super article je trouve.
• Credit Card Fraud Detection: A Realistic Modeling and a Novel Learning Strategy (2018)
• Combining unsupervised and supervised learning in credit card fraud detection (2019)
• Anomaly Detection using Unsupervised Methods: Credit Card Fraud Case Study (2019)
  • « However, normal transaction labels are needed for most of the unsupervised methods so machine learning techniques would be trained on normal transaction so it can differentiate between normal and fraud for the upcoming transactions. » Nous on veut un algorithme qui n’a pas du tout besoin de labels.
  • Les données consistent en 28 composantes principales (pour raisons de confidentialité) + « time » et « amount ». Probablement le jeu de données Kaggle.
  • Utilisent un One-Class SVM, un auto-encodeur et la méthode de Mahalanobis pour la classification. Pour le One-class SVM et pour l’auto-encodeur, on a besoin de savoir quelles sont les observation normale. Seule la méthode de Mahalanobis est complètement non-supervisée.
  • Méthode de Mahalanobis:
    • Pour chaque observation, on calcule la distance de Mahalanobis (mesure la distance entre l’obseravtion et la distribution empirique). Ensuite, on peut tracer un graphique « distance-distance » pour repérer les anomalies, ou bien se donner un « threshold » et dire que toutes les observations qui dépassent ce threshold sont des anomalies.
    • Pas un super article je trouve.
    • 
• Autoencoding Credit Card Fraud
  • Utilisation d’auto-encodeurs (donc non-supervisé) pour détecter les anomalies et donc les fraudes de cartes de crédit.
  • Les données consistent en 28 composantes principales (pour raisons de confidentialité) + « time » et « amount ». Probablement le jeu de données Kaggle.
  • Bien qu’il font de l’apprentissage non-supervisé, ils ont quand même les labels pour chaque transaction. Ils disent qu’ils entrainent leurs auto-encodeurs seulement sur les données « normales » (donc non-frauduleuses). Donc finalement, est-ce qu’on peut vraiment appeler ça de l’apprentissage non-supervisé?
  • Thèse de niveau baccalauréat
• Unsupervised Learning for Robust Bitcoin Fraud Detection
  • Utilisent un jeu de données de 37 millions de transactions de Bitcoins reliées à 6 millions d’utilisateurs.
  • Ils créent des features reliées aux utilisateurs. Donc on veut déterminer les utilisateurs anormaux.
  • • 
  • Complètement non-supervisé.
  • Utilisent du K-means clustering et du Trimmed K-means clustering. Ils réussissent à trouver 5 des 30 utilisateurs frauduleux de la base de données.
• Credit Card Fraud Detection in e-Commerce: An Outlier Detection Approach (2019)
  • Code disponible ici
  • Méthode qui n’a pas besoin du tout de labels.
  • En gros, on ajuste un k-means clustering N fois sur les données avec différentes valeurs de k. Ça donne N centroïdes pour chaque observation. On calcule finalement un « score de cohérence » pour chaque observation à partir de ces N centroïdes.
  • Ils testent leur méthode sur différent jeux de données, dont le jeu de données Kaggle de détection de fraudes de cartes de crédit.
• Isolation Forest (2008)
• LOF: Identifying Density-Based Local Outliers (2000)
• Automatic Hyperparameter Tuning Method for Local Outlier Factor, with Applications to Anomaly Detection
  • Proposent une méthode heuristique pour choisir k (le nombre de voisins) et c (le pourcentage d’anomalies) de manière jointe.
  • Le problème avec cette méthode est qu’elle donne un k optimal pour un c fixe. Nous, on ne veut pas avoir à choisir une valeur pour c.

14 UMAP

15 Local Outlier Factors

• Technique qui permet d’assigner une mesure du degré d’anormalité à chaque point d’un jeu de données.
• Technique intéressante car non dichotomique (ce n’est pas tout blanc ou tout noir).
• Technique intéressante car elle permet de détecter les anomalies locales (et pas seulement globales).
• Fonctionne bien en plusieurs dimensions.
• Fonctionne en comparant la densité locale d’un point avec la densité locale de son voisinage.
• Inconvénient: la valeur obtenue pour chaque point est un quotient qui est difficile à interpréter.

Fonctionnement

• Il faut d’abord choisir k, le nombre de voisins, qui est un hyperparamètre.
• Ensuite, on calcule pour chaque point la local reachability density, c’est-à-dire l’inverse de la distance typique (ou moyenne) à laquelle le point peut être « atteint » par ses k voisins. Donc moins le point est atteignable par ses voisins (donc distance élevée), plus la densité sera faible. Ici la reachability-distance est une distance définie par l’auteur pour que l’algorithme soit plus stable: on aurait pu aussi utiliser la distance euclidienne. En mots, la formule suivante calcule l’inverse de la reachability-distance moyenne de A à partir de ses k voisins. Noter que la reachability-distance n’est pas une distance au sens mathématique du terme car non symétrique.
  • 
  • En termes plus simples, plus les k voisins de A sont éloignés (proches), plus la densité locale de A sera faible (élevée).
• Finalement, pour calculer le local outlier factor (LOF) pour chaque point A, on compare sa local reachability density avec la local reachability density moyenne de ses k voisins (on divise la local reachability density moyenne des k voisins par la local reachability density de A).
  • 
  • Si LOF(A) > 1, A est un outlier parce que sa densité locale est plus petite que celle de ses voisins.
  • Si LOF(A) < 1, A est un inlier parce que sa densité locale est plus grande que celle de ses voisins.

Exemple des scores obtenus sur un jeu de données en 2 dimensions

16 Notes

• Est-ce qu’on a vraiment des données de type « time series »? Le prix d’une action au cours du temps est clairement une série temporelle parce que le prix au temps x est fortement dépendant du prix au temps x - 1. La température à chaque jour aussi. Avec les données de trajets qu’on a, il n’y a pas trop de dépendance temporelle je pense. La distance parcourue le 29 janvier n’est pas si dépendante de la distance parcourue le 28 janvier. On serait peut-être plus dans « détection d’anomalies multivariée » plutôt que dans « détection d’anomalies dans les séries temporelles ».

• Est-ce qu’on devrait agréger un peu les données? Par jour? Par semaine?

• Pour les variables encodées de manière circulaire: ce ne sont pas des variables ordinaires, donc il faut probablement faire attention à la manière dont on les modélise.

• Répétition d’information 2 variables cycliques?

• Une fois qu’on a déterminé les trajets anormaux (ou un score d’anormalité pour chaque trajet) pour un assuré, on fait quoi avec? On essaie de créer une feature avec pour donner en entrée à de l’apprentissage supervisé de réclamations?

• En utilisant la méthode LOF, on peut calculer un score d’anomalie pour chaque trajet. Ensuite on voudrait utiliser ces scores d’anomalie pour la prédiction de réclamations.

  • Comment on donne en entrée ces scores aux modèles? En calculant des statistiques pour chaque véhicules? Du genre « moyenne du score d’anomalie », « variance de score d’anomalie », etc.
  • Est-ce qu’il y aurait moyen de ne pas résumer l’information et de donner la distribution complète des scores d’anomalie aux modèles? Peut-être avec un réseau de neurones. Cependant, chaque véhicule a un nombre différent de trajets. On pourrait donner en entrée aux modèles des histogrammes des scores.